As a conventional data transformation method for encryption, “FEAL-8 Algorithm” (Fast data Encipherment ALgorithm-8) is disclosed by Miyaguchi et al. (Miyaguchi, Shiraishi, and Shimizu, “FEAL-8 Encipherment Algorithm” NTT Practical Research Report vol. 39, No. 4/5, 1988).
FIG. 29 is a partial diagram of the above “FEAL-8” encipherment algorithm.
In the figure, 1001 and 1002 denote input data of two sequences, 1003 and 1004 denote output data of two sequences, and 1005, 1006, 1007 and 1008 denote intermediate data. 1011, 1012, 1013 and 1014 respectively show a first key parameter, a second key parameter, a third key parameter and a fourth key parameter. Each of 1021, 1022, 1023 and 1024 shows sub-transformation unit of each transforming stage. Each sub-transformation unit includes each of nonlinear transformers 1031, 1032, 1033, 1034 and each of XOR (exclusive OR) circuits 1041, 1042, 1043, 1044.
An operation will be explained hereinafter. The input data 1001 and 1002 of two sequences are received at the sub-transformation unit 1021 of a first stage to be transformed into new data, that is, the intermediate data 1005 and 1006 of two sequences. The intermediate data is input to the sub-transformation unit 1022 of a second stage to be transformed into new data, that is, the intermediate data 1007 and 1008. The above operation is repeated eight times in total, and the output data 1003 and 1004 of two sequences are output as the last transformation result from the sub-transformation unit of an eighth stage.
An operation of the sub-transformation unit 1021 of the first stage will be explained for one example of the above sub-transformation units.
The sub-transformation unit 1021 receives the input data 1001 and 1002 of two sequences and outputs the intermediate data 1005 and 1006 of two sequences. As described in detail in the above Practical Research Report, the second input data, that is, the input data 1002, is divided into byte by byte, and the divided is then XORed with the key parameter. Arithmetic addition is repeated to the data and the divided data is united again. This nonlinear transforming operation is performed in the nonlinear transformer 1031. The transformed data is XORed with the first input data 1001. The XORed result is output from the first stage as the second intermediate data 1006. On the other hand, the second input data 1002 is output as the first intermediate data 1005 without any transformation.
In the second sub-transformation unit 1022, data is processed as well as in the above procedure and the intermediate data of the second stage is obtained. In the same way, in this example, the processes of eight stages are performed in total. As the result, output data 1003 and 1004 are obtained.
The conventional data transformation apparatus is configured as described above. The transformed data is output only after the nonlinear transformation is completed in one stage of the sub-transformation unit, and is input to the sub-transformation unit of the next stage. Namely, each sub-transformation is performed sequentially and it takes time to perform an entire procedure.
The present invention is provided to solve the above problem. The object of the invention is to perform a plurality of sub-transformations in parallel to increase the processing speed of data transformation such as encryption, decryption and data diffusion.
The data transformation apparatus of the present invention inputs two arbitrary pieces of data of A input data and B input data to a first unit of the apparatus. A first nonlinear transformation of A input data is performed using a first key parameter and the transformed data is XORed with B input data. The XORed result is output as B intermediate data. B input data is also output as A intermediate data without any transformation. In a next unit, a second nonlinear transformation of A intermediate data is performed using a second key parameter and the transformed data is XORed with B intermediate data. The XORed result is output as next B intermediate data. B intermediate data output from the first unit is output as next A intermediate data without any transformation. The above two units are connected in a cascade and the last A intermediate data and the last B intermediate data are output as transformation result of the data transformation apparatus.
Further, in the above basic configuration of the apparatus, a set of a first nonlinear transformer and an XOR circuit located between an input side of the first nonlinear transformation and an input side of the second nonlinear transformation is defined as a first sub-transformation unit. Another set of a second nonlinear transformer and an XOR circuit located between the input side of the second nonlinear transformation and the input side of the first nonlinear transformation of the next stage is defined as a second sub-transformation unit. Otherwise, a set of the XOR circuit and the second nonlinear transformer located between an output side of the first nonlinear transformation and an output side of the second nonlinear transformation is defined as the first sub-transformation unit. Another set of the XOR circuit and the first nonlinear transformer located between the output side of the second nonlinear transformation and the output side of the first nonlinear transformation of the next stage is defined as the second sub-transformation unit. Regardless of the definition, a necessary number of the above first sub-transformation units and the second sub-transformation units are alternately connected in a cascade. From the last stage, A intermediate data and B intermediate data output from either of the first and the second sub-transformation units is output as the transformation result of the apparatus.
Further, the nonlinear transformer of each sub-transformation unit has a nest configuration of the basic configuration of data transformation apparatus.
According to a data transformation method of the present invention, two arbitrary pieces of data of A input data and B input data are input. B input data is output as a first A intermediate data at a first step. A nonlinear transformation of A input data is performed using a first key parameter. The transformed data is XORed with B input data and the XORed result is output as a first B intermediate data at a second step. At a third step, the first B intermediate data is input and output as a second A intermediate data. The first A intermediate data is input and a nonlinear transformation of the A intermediate data is performed using a second key parameter. The transformed data is XORed with the first B intermediate data and the XORed result is output as a second B intermediate data at a fourth step. The above steps are repeated from the first step to the fourth step. The above second step or the fourth step should be placed at the last step of the transformation method and the last A intermediate data and the last B intermediate data are output as the transformation result of the whole procedure.
In the above method, an operation order may be changed, that is, a nonlinear transformation and an XOR operation may be altered. The method still have effective steps as the above.
Further, in the above basic configuration of the apparatus, a set of the first nonlinear transformer and the XOR circuit located between the input side of the first nonlinear transformation and the input side of the second nonlinear transformation is defined as the first sub-transformation unit. Another set of the second nonlinear transformer and the XOR circuit located between the input side of the second nonlinear transformation and the input side of the first nonlinear transformation of the next stage is defined as the second sub-transformation unit. Otherwise, a set of the XOR circuit and the second nonlinear transformer located between the output side of the first nonlinear transformation and the output side of the second nonlinear transformation is defined as the first sub-transformation unit. Another set of XOR circuit and the first nonlinear transformer located between the output side of the second nonlinear transformation and the output side of the first nonlinear transformation of the next stage is defined as the second sub-transformation unit. Regardless of the definition, a necessary number of the above first sub-transformation units and the second sub-transformation units are alternately connected in a cascade. A data selecting unit is provided to the input side of the first sub-transformation unit and a data holding unit is also provided to the output side of either of the first and the second sub-transformation units. At the beginning of the data transformation, the data selecting unit selects one of two arbitrary pieces of data of A input data and B input data. After selecting one input data, the data selecting unit is connected with the data holding unit to form a feedback loop so as to select the output of the data holding unit. The selected data is transformed to be finally output from either of the first and the second sub-transformation units and is stored in the data holding unit. Then, A intermediate data and B intermediate data are output from the data holding unit as the transformation result of the apparatus.
Further, in the above basic configuration of the data transformation apparatus, the two arbitrary pieces of data of A input data and B input data include the same number of digits of data. Either of a set of the first nonlinear transformer and the XOR circuit located between the input side of the first nonlinear transformation and the input side of the second nonlinear transformation and a set of the second nonlinear transformer and the XOR circuit located between the output side of the second nonlinear transformation and the output side of the first nonlinear transformation is defined as a sub-transformation unit. A necessary number of the sub-transformation units are connected. The data selecting unit is provided to each of the two input sides of A input data and B input data of the first sub-transformation unit. The data holding unit is provided to each of the two output sides of A output data and B output data of the last sub-transformation unit. As a first step of the data transformation procedure, the data selecting units select A input data and B input data, respectively. After selecting the input data, the data selecting unit is connected with the data holding unit to form the feedback loop so as to select the output of the data holding unit. The selected data is transformed and, finally, the data holding unit outputs A intermediate data and B intermediate data as the transformation result.
Further, in the first or the second nonlinear transformation, A input data is divided into A1 input data including some digits of A input data and A2 input data including the other digits of A input data. The key parameter is also divided by an arbitrary number of digits into “n” number of divided key parameters, from a first divided key parameter to an n-th divided key parameter. In a first internal sub-transformation unit, an internal nonlinear transformation of A1 input data, that is, one of the divided A input data, is performed using the first divided key parameter. The transformed data is XORed with the A2 input data and the XORed result is output as first A2 internal intermediate data. A2 input data is output as first A1 internal intermediate data without any transformation. The first A1 internal intermediate data output from the first internal sub-transformation unit is input to a second internal sub-transformation unit as A1 input data. An internal nonlinear transformation of the first A1 internal intermediate data is performed using the second divided key parameter. The first A2 internal intermediate data, input as A2 input data, is XORed with the transformed first A1 internal intermediate data. The XORed result is output as second A2 internal intermediate data and the first A2 internal intermediate data is output as second A1 internal intermediate data without any transformation. The above first internal sub-transformation unit and the second internal sub-transformation unit are alternately connected “n” times. An internal data selecting unit is provided to the input side of the first internal sub-transformation unit and an internal data holding unit is provided to either of the output sides of the first and the second internal sub-transformation units. The internal data selecting unit selects A1 input data and A2 input data. After selecting the input data, the internal data selecting unit is connected with the internal data holding unit to form the feedback loop so as to select the output of the internal data holding unit. The selected data is transformed and, finally, A1 internal intermediate data and A2 internal intermediate data is output from the internal data holding unit as the transformed A output data.
Further, in the nonlinear transformation of each sub-transformation unit, A input data is divided into A1 input data including some digits of A input data and A2 input data including the other digits of A input data. The key parameter is also divided by an arbitrary number of digits into “n” number of divided key parameters, from a first divided key parameter to an n-th divided key parameter. In the first internal sub-transformation unit, an internal nonlinear transformation of A1 input data, that is, one of the divided A input data, is performed using the first divided key parameter. The transformed data is output as first A2 internal intermediate data. A1 input data is XORed with the A2 input data and the XORed result is output as first A1 internal intermediate data. In the second internal sub-transformation unit, an internal nonlinear transformation of the first A1 internal intermediate data, output from the first internal sub-transformation unit and input as A1 input data, is performed using the second divided key parameter. The transformed data is output as second A2 internal intermediate data. An XOR operation of the first A1 internal intermediate data and the first A2 internal intermediate data is performed as A1 input data and A2 input data. The XORed result is output as second A2 internal intermediate data and the first A2 internal intermediate data is output as second A1 internal intermediate data. The above first internal sub-transformation unit and the second internal sub-transformation unit are alternately connected “n” times. The internal data selecting unit is provided to each of the input sides of the first internal sub-transformation unit and the internal data holding unit is provided to either of the output sides of the first and the second internal sub-transformation units. The internal data selecting unit selects A1 input data and A2 input data. After selecting the input data, the internal data selecting unit is connected with the internal data holding unit to form the feedback loop so as to select the output of the internal data holding unit. The selected data is transformed and, finally, A1 internal intermediate data and A2 internal intermediate data are output from the internal data holding unit as the transformed A output data.
Further, in both of the above two kinds of modification of the data transformation apparatus, when A input data is divided into two pieces of divided input data having the same number of digits, only the first internal sub-transformation unit is connected necessary number of times.
Further, the first internal sub-transformation unit and the second internal sub-transformation unit are alternately connected necessary number of times. The internal data selecting unit is provided to the input side of the first internal sub-transformation unit and the internal data holding unit is provided to the output side of either of the first and the second internal sub-transformation units. As a first step of the data transformation, the internal data selecting unit selects B1 input data and B2 input data. After selecting the input data, the internal data selecting unit is connected with the internal data holding unit to form the feedback loop so as to select the output of the internal data holding unit. The selected data is transformed and, finally, B1 internal intermediate data and B2 internal intermediate data are output from the internal data holding unit as the transformed B output data.
Further, in the above configuration, when B input data is divided into two divided input data having the same number of digits, only the first internal sub-transformation unit is connected necessary number of times.
Further, in the data transformation apparatus, the sub-transformation units are connected even number of times. The data selecting unit is provided to the input side of the first sub-transformation unit and the data holding unit is provided to the output side of the last sub-transformation unit. A key parameter supply unit is also provided to the above configuration. As a first step of the data transformation, the data selecting unit selects two arbitrary pieces of data of A input data and B input data. After selecting the input data, the data selecting unit is connected with the data holding unit to form the feedback loop so as to select the output of the data holding unit. The data transformation apparatus repeatedly transforms the selected data using the key parameters, each of which is supplied by the key parameter supply unit to each of the sub-transformation units. The data holding unit finally outputs A intermediate data and B intermediate data as the transformation result.
Further, in the above configuration, at least one of the nonlinear transformers is Xn (X: an element) circuit on Galois Field.
Further, the above Xn circuit on Galois Field is formed by a normal basis.
Further, in the above configuration, at least one part of the nonlinear transformer is a Read Only Memory.
Further, in the above configuration, at least one part of the nonlinear transformer is a Random Access Memory.
Further, in the above configuration, at least one part of the nonlinear transformer is a Logic Circuit.
Further, a data transformer including two logic circuits is provided to at least one of A input and B input. Each of the above two logic circuits may be either of two XOR circuits and AND circuit and OR circuits. A input data or B input data is divided into two pieces of divided data having an arbitrary number of digits such as AA data and AB data. The key parameter is divided into two divided key parameters, A transformation key parameter and B transformation key parameter. A first AND/OR operation of AA data and A transformation key parameter is performed. The first ANDed/ORed result is first XORed with the AB data and the first XORed result is output as the transformation result of AB data. The first XORed result is second ANDed/ORed with B transformation key parameter. A second XOR operation of the second ANDed/ORed result and AA data is performed and the second XORed result is output as the transformation result of AA data. The transformed AA data and the transformed AB data are output to the next stage as A input data or B input data.